package org.example.BinaryTree;

import java.util.HashMap;

public class Construct_binary_tree_2 {
    public static HashMap<Integer,Integer> hashMap = new HashMap<>();
    public static void main(String[] args) {
        //从前序与中序遍历序列构造二叉树

        //给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
        int[] preorder = {1,2,3};
        int[] inorder = {2,3,1};
        search(buildTree(preorder,inorder));
    }
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            hashMap.put(inorder[i],i);
        }
        return getNode(preorder,0, preorder.length-1, inorder,0,inorder.length-1);
    }
    public static TreeNode getNode(int[] preorder,int beginPre,int endPre,int[] inorder,int beginIn,int endIn){
        if (beginPre>endPre || beginIn>endIn) return null;
        TreeNode node = new TreeNode(preorder[beginPre]);
        Integer index = hashMap.get(node.val);
        int lenofleft = index - beginIn;
        node.left = getNode(preorder,beginPre+1,beginPre+lenofleft,inorder,beginIn,beginIn+lenofleft);
        node.right = getNode(preorder,beginPre+lenofleft+1,endPre,inorder,index+1,endIn);
        return node;
    }
    public static void search(TreeNode root){
        if (root==null) return;
        System.out.println(root.val);
        search(root.left);
        search(root.right);
    }
}
